package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-07-21 15:52
 * @description: Functions of this class is
 **/
public class 双指针找寻第一个公共节点 {
    //双指针法找到第一个相交的节点
    private static class ListNode{
        int val;
        ListNode next;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ha=headA;
        ListNode hb=headB;
        while (ha!=hb){
            ha=(ha==null)?headB:ha.next;
            hb=(hb==null)?headA:hb.next;
        }
        return ha;
    }
    /**
     *
     这是「差值法」的另外一种实现形式，原理同样利用「两条链表在相交节点后面的部分完全相同」。
     我们令第一条链表相交节点之前的长度为 a，第二条链表相交节点之前的长度为 b，相交节点后的公共长度为 c（注意 c 可能为 00，即不存在相交节点）。

     分别对两条链表进行遍历：

     **当第一条链表遍历完，移动到第二条链表的头部进行遍历；

     **当第二条链表遍历完，移动到第一条链表的头部进行遍历。
     如果存在交点：第一条链表首次到达「第一个相交节点」的充要条件是第一条链表走了 a + c + ba+c+b 步，
     由于两条链表同时出发，并且步长相等，因此当第一条链表走了 a + c + ba+c+b 步时，
     第二条链表同样也是走了 a + c + ba+c+b 步，即 第二条同样停在「第一个相交节点」的位置。
     */

}